package com.demo.datastructure.reorder.quickSort;

import com.demo.datastructure.reorder.Example;

/**
 * @author ljr
 * @version 1.0
 * @description: 快排练习
 * 注意：在数组容量较小的情况下， 插入排序比快速排序快
 * @date 2022/1/19 12:39
 */
public class SimpleQuickSort4 implements Example {

    @Override
    public void sort(Comparable[] a, int low, int high) {
        if(low >= high) return;
        int mid = partition(a, low, high);
        sort(a, low, mid-1);
        sort(a, mid+1, high);
    }

    private int partition(Comparable[] a, int low, int high) {
        Comparable lastValue = a[high];
        int min = low;

        /**
         * 采用插入排序的思想
         * 用一个指针来记录小于选中数的下一个位置、
         * 如果在循环中继续出现小于选中数的情况，
         * 则把它和该指针数据进行交换，并将指针数加1
         */
        for(int i = low; i < high; i++){
            if(less(a[i], lastValue)){
                Comparable value = a[i];
                a[i] = a[min];
                a[min++] = value;
            }
        }

        a[high] = a[min];
        a[min]= lastValue;
        return min;
    }
}
